/**
 * 单项链表
 * - 单向链表是由一系列节点组成的数据结构，每个节点包含一个数据域和一个指向下一个节点的指针。
 * - 最后一个节点的指针指向 null，表示链表的末尾。
 * 单项列表的每一个节点都认为自己是链表的头节点，因为它没有前驱节点。
 */
class SinglyLink {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

let singlyL1 = new SinglyLink(1);
let singlyL2 = new SinglyLink(2);
let singlyL3 = new SinglyLink(3);
let singlyL4 = new SinglyLink(4);
singlyL1.next = singlyL2;
singlyL2.next = singlyL3;
singlyL3.next = singlyL4;

/**
 * 遍历树形结构的节点
 * @param {Object} root - 树形结构的根节点
 */
function ergodic(root) {
  if (root == null) return;
  console.log("▶『singlyL』", root.value);
  ergodic(root.next);
}

ergodic(singlyL1); // 遍历链表


/**
 * 反转链表
 * 给定一个链表，返回反转后的链表头节点
 * @param {ListNode} root - 链表的头节点
 * @return {ListNode} - 反转后的链表的头节点
 */
function nz(root) {
  if (root == null) return;
  if (root.next == null) return root;
  let temp = nz(root.next);
  root.next.next = root;
  root.next = null;
  return temp;
}

ergodic(nz(singlyL1)); // 逆置链表后遍历


/**
 * 双向链表
 * - 双向链表也是由一系列节点组成的数据结构，每个节点包含一个数据域、一个指向前一个节点的指针和一个指向下一个节点的指针。
 * - 双向链表的头部和尾部节点的指针分别指向 null，表示链表的开头和末尾。
 */

class DoublyLink {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

let doublyL5 = new DoublyLink(5);
let doublyL6 = new DoublyLink(6);
let doublyL7 = new DoublyLink(7);
let doublyL8 = new DoublyLink(8);
doublyL5.next = doublyL6;
doublyL6.prev = doublyL5;
doublyL6.next = doublyL7;
doublyL7.prev = doublyL6;
doublyL7.next = doublyL8;
doublyL8.prev = doublyL7;
